package com.LeeCode;

/**
 * 二叉树任务调度
 */

public class CodeLCP010 {
    public static void main(String[] args) {
        Integer[] arr = {1, 3, 2, null, null, 4, 4};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new CodeLCP010().minimalExecTime(root));
    }

    class Result {
        int total;     // 所有任务时间之和
        double optimal; // 双核最优执行时间

        Result(int total, double optimal) {
            this.total = total;
            this.optimal = optimal;
        }
    }

    public Result dfs(TreeNode root) {
        if (root == null) {
            return new Result(0, 0.0);
        }

        Result left = dfs(root.left);
        Result right = dfs(root.right);

        int a = left.total;
        double b = left.optimal;
        int c = right.total;
        double d = right.optimal;

        int tot = a + c + root.val;

        // 判断是否可以合并优化
        if ((c - 2 * d <= a && a <= c) || (a - 2 * b <= c && c <= a)) {
            return new Result(tot, (a + c) / 2.0);
        }

        if (a - 2 * b > c) {
            return new Result(tot, b + c);
        } else {
            // c - 2 * d > a
            return new Result(tot, a + d);
        }
    }

    public double minimalExecTime(TreeNode root) {
        Result p = dfs(root);
        return p.total - p.optimal; // 或者直接返回 p.optimal ?
    }

}
